package com.github.hgkmail.hello.leetcode101.sort;

import com.github.hgkmail.hello.leetcode101.base.CommonUtil;

import java.util.Arrays;

public class LC75SortColors {
    //左闭右开
    public int partition(int[] nums, int l, int r) {
        int key=nums[l];
        int i=l;
        int j=r-1;
        while (i<j) {
            while (i<j && nums[j]>=key) j--; //j--写在前面
            while (i<j && nums[i]<=key) i++;
            if (i<j) {
                CommonUtil.swap(nums, i, j);
            }
        }
        CommonUtil.swap(nums, l, i);
        return i;
    }
    public void quicksort(int[] nums, int l, int r) {
        if (l+1>=r) {
            return;
        }
        int pivot = partition(nums, l, r);
        quicksort(nums, l, pivot);
        quicksort(nums, pivot+1, r);
    }

    public void sortColors(int[] nums) {
        quicksort(nums, 0, nums.length);
    }

    public static void main(String[] args) {
        int[] nums = new int[]{2,0,2,1,1,0};
        new LC75SortColors().sortColors(nums);
        System.out.println(Arrays.toString(nums));
    }
}
